package J3_4;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class test {

    //你的笔记本键盘存在故障，每当你在上面输入字符 'i' 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。
    //
    //给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。
    //
    //返回最终笔记本屏幕上输出的字符串。

    public String finalString(String s) {
        Deque<Character> deque = new LinkedList<>();
        Boolean follow = true;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'i') {
                follow = !follow;
            } else if (follow) {
                deque.offerFirst(s.charAt(i));
            } else {
                deque.offerLast(s.charAt(i));
            }
        }
        StringBuilder str = new StringBuilder();
        if (follow) {
            while (!deque.isEmpty()) {
                str.append(deque.pollLast());
            }
        } else {
            while (!deque.isEmpty()) {
                str.append(deque.pollFirst());
            }
        }
        return str.toString();
    }



    //有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：
    //
    //每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
    //Alice 将会取走硬币数量最多的那一堆。
    //你将会取走硬币数量第二多的那一堆。
    //Bob 将会取走最后一堆。
    //重复这个过程，直到没有更多硬币。
    //给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。
    //
    //返回你可以获得的最大硬币数目。
    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int n = piles.length/3;
        int coins = 0;
        for (int i = n; i < piles.length; i+=2) {
            coins += piles[i];
        }
        return coins;
    }


    //给你一个正整数 n ，请你返回 n 的 惩罚数 。
    //
    //n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：
    //
    //1 <= i <= n
    //i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。
    public int punishmentNumber(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (isPunishmentNumber(i)) {
                sum = sum+i*i;
            }
        }
        return sum;
    }

    private boolean isPunishmentNumber(int i) {
        return recall(Integer.toString(i*i),0,0,i);
    }

    private boolean recall(String str, int i, int sum, int a) {
        if (i == str.length()) {
            return sum==a;
        }
        int tot = 0;
        for (int j = i; j < str.length(); j++) {
            int num = str.charAt(j) - '0';
            tot = tot*10+num;
            if (tot+sum > a) {
                break;
            }
            if (recall(str,j+1,sum+tot,a)) {
                return true;
            }
        }
        return false;
    }

}
